%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graph-theory-algorithms-book/
%%
%% Copyright (C) 2009--2011 Minh Van Nguyen <nguyenminh2@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\DontPrintSemicolon
\SetAlgoNoLine
%%
%% data
\SetKwData{NULL}{\footnotesize{NULL}}
%%
%% input
\KwIn{A Polish stack $P$ containing an arithmetic expression in
  reverse Polish notation.}
%%
%% output
\KwOut{An evaluation of the arithmetic expression represented by $P$.}
\BlankLine
%%
%% algorithm body
$E \assign$ empty stack\;
$v \assign \NULL$\;
\While{\rm $P$ is not empty}{
  $x \assign \pop(P)$\;
  \If{\rm $x$ is an operator}{
    $b \assign \pop(E)$\;
    $a \assign \pop(E)$\;
    \If{\rm $x$ is addition operator}{
      $v \assign a + b$\;
    }
    \ElseIf{\rm $x$ is subtraction operator}{
      $v \assign a - b$\;
    }
    \ElseIf{\rm $x$ is multiplication operator}{
      $v \assign a \times b$\;
    }
    \ElseIf{\rm $x$ is division operator}{
      $v \assign a / b$\;
    }
    \Else{
      exit algorithm with error\;
    }
    $\push(E, v)$\;
  }
  \Else{
    $\push(E, x)$\;
  }
}
$v \assign \pop(E)$\;
\Return $v$\;
